import java.util.*;
public class Text {
      public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
  //反转链表
    //采用三个指针！
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode cur = head.next;
        ListNode curNext = null;
        head.next = null;
        while(cur != null){
            curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    /*
    题目2 ： 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
     */
    public ListNode deleteDuplicates(ListNode head) {
        //没有元素时：
        if(head == null){
            return null;
        }
        //只有一个元素时：
        if(head.next == null){
            return head;
        }
        //大于等于两个元素时:
        ListNode cur = head;
        ListNode curNext = cur.next;
        while(curNext != null){
            if(cur.val == curNext.val){
                cur.next = curNext.next;
                curNext = cur.next;
            }else{
                cur = curNext;
                curNext = cur.next;
            }
        }
        return head;
    }

    /*
    题目 3 ：有效括号
     */
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        for(char x : s.toCharArray()){
            if(x == '(' || x == '[' || x == '{'){
                stack.push(x);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                char ch = stack.pop();
                if(x == ')' && ch != '(' || x == ']' && ch != '[' || x == '}' && ch != '{'){
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }
}
